package com.stanley.alogrithm

object Solution {

    @JvmStatic
    fun main(args: Array<String>) {
        var n = 5
        var v = 6
        var array:IntArray = intArrayOf(1, 2, 4, 5, 6)
        var result = upper_bound_(n, v, array)
        println("The value $v position is $result")
    }

    fun upper_bound_(n: Int,v: Int,a: IntArray): Int  {

        // write code here
        if( n == 1) {
            var first = a[0]
            when(first >= v) {
                true -> return 0
                else -> return n + 1
            }
        }
        var targetIndex = n + 1
        var begin = 0
        var middle = n/2
        var end = n - 1
        if (a[begin] >= v ) {
            return 1
        }
        if( a[end] < v) {
            return targetIndex
        }

        var currentValue = 0
        while (middle in 0 until n) {
            if (middle == begin) {
                if (a[begin] >= v) {
                    return begin + 1
                } else {
                    return end + 1
                }
            }
            currentValue = a[middle]
            if (currentValue < v) {
                begin = middle
                middle = (begin + end )/2
            } else {
                if(middle - 1 >= 0 && a[middle -  1] < v) {
                    targetIndex = middle + 1
                    break
                }
                end = middle
                middle = (begin + end)/2
            }
        }



        return targetIndex
    }
}